package com.fantaike.algorithm.symbol;

import lombok.Data;

import java.util.HashMap;
import java.util.Iterator;

/**
 * 符号表
 * @author jishushen
 * @create 2021-11-02 21:48
 */
public class SymbolTable<Key,Value> implements Iterable{
    //记录首节点的位置
    private Node head;
    //元素的个数
    private int N;

    @Data
    public class Node{
        //键
        public Key key;
        //值
        public Value value;
        //下一个节点
        private Node next;

        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public SymbolTable(){
        head = new Node(null,null,null);
        N = 0;
    }

    //获取元素的个数
    public int size(){
        return N;
    }

    //向符号表中进行插入
    public void put(Key key,Value value){
        Node n = head;
        //先从符号表中查找键为key的键值对
        while (n.next != null){
            //变换n
            n = n.next;
            //判断n节点存储的key是否存在，存在就将里面的值替换
            if (n.key.equals(key)){
                n.value = value;
                return;
            }
        }
        //符号表中如果没有Key的键值对，使用头插法进行插入
        Node newNode = new Node(key,value,null);
        //获取头节点的下一个节点
        Node oldNode = head.next;
        //将新节点的下一个节点指向这个老节点
        newNode.next = oldNode;
        //头结点的下一个节点为新节点
        head.next = newNode;
        //元素个数+1
        N++;
    }

    //删除符号表中键为Key的值
    public void delete(Key key){
        //将head赋值给一个变量进行遍历
        Node n = head;
        //进行遍历，找到键为key值删除掉
        while (n.next != null){
            if (n.next.key.equals(key)){
                //将n的下一个节点指向下下节点
                n.next = n.next.next;
                //元素个数减-
                N--;
                return;
            }
            //变换n
            n = n.next;
        }
    }

    //从符号表中获取key对应的value
    public Value get(Key key){
        //将head赋值一个变量
        Node n = head;
        while (n.next != null){
            //变换n
            n = n.next;
            //如果key相等就将value返回去
            if (n.key.equals(key)){
                return n.value;
            }
        }
        return null;
    }

    @Override
    public Iterator iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator{

        private Node node;

        public SIterator(){
            this.node = head;
        }

        @Override
        public boolean hasNext() {
            return node.next != null;
        }

        @Override
        public Object next() {
            node = node.next;
            return new HashMap<Key,Value>(){{
                put(node.key,node.value);
            }};
        }
    }
}
